The present invention relates to apparatus for performing the discrete Fourier transform (DFT). There are various known algorithms for reducing the discrete Fourier transform for N points to manageable proportions where N is large, say of the order of 1000 or larger. Some such algorithms are described in the chapter "Discrete Fourier Transforms" in the book "Digital Processing of Signals" by Gold and Rader, Mc-Graw-Hill 1969. The DFT Proceeds in a series of levels in each of which a new set of points is created from an old set of points by performing a plurality of elementary DFTs. The points are, in general, complex quantities although the first old set, i.e. the input set, and the last new set, i.e. the output set, may well be real quantities, eg in transforming time samples of a waveform to frequency spectrum components or vice versa.
In a version of the algorithm well-known as the Colley-Tukey algorithm or fast Fourier transform, in which N=2.sup.P and there are P levels, each elementary DFT consists in forming a pair of new points from a pair of old points by forming sum and difference values from the old points multiplied by coefficients which are powers of e.sup.-(2.pi./N). Other versions of the DFT algorithm, such as the Winograd algorithm, require N to be the product of a plurality of small numbers which are prime relative to each other. For example, the embodiment of the invention which is descirbed below has EQU N=840=3.times.5.times.7.times.8.
A larger value of N is given by EQU N=1260=4.times.5.times.7.times.9.
In this class of algorithm, where the small relatively prime numbers are q, r etc., one level performs N/q q-point DFTs, another performs N/r r-point DFTs, and so on. For the general case of an n-point DFT, an n-point old vector has to be multiplied by an n by n matrix to form an n-point new vector. The matrix values, like the vector points, are in general complex. A further known simplification consists in decomposing the matrix into the product of three matrices of which the first contains 0 and 1 values only, the second of which is a diagonal matrix with diagonal values each of which is either only real or only imaginary and the third of which again contains 0 and 1 values only.
The foregoing description has been provided by way of a brief background of the invention which is not concerned with the nature of the DFT algorithm and is intended for use with any such algorithm. Neither is the invention concerned with the means used to implement the elementary DFTs and such means will not be described. These means will typically consist of a microprocessor programmed in accordance with the equations given in Gold and Rader, loc. cit. although a hardware implementation is naturally possible.
The invention is concerned with a problem which is well known in relation to DFTs and explained for example in Gold and Rader. This problem is jumbling of the output points relative to the input points. Although this problem can be dealt with by accepting a jumbled output set which has to be re-ordered or by so pre-jumbling the input set that the output set is in the right order, it is preferred for many purposes to deal with the problem by altering, in at least some levels of the computation, the addresses of the new points relative to the addresses of the old points. A simple example of the technique is illustrated in FIG. 6.12 of Gold and Rader and British patent specification No 1407401 describes in some detail a specific implementation of the technique as applied to the Cooley-Tukey type of algorithm.
Although the jumbling is always orderly and its nature can be calculated, the address reordering required for a Winograd type algorithm cannot be achieved by a simple, iterated bit-reversal rule such as is described in the British patent specification mentioned above. Furthermore, it is desirable to be able to utilize the same basic apparatus to perform any of a set of different DFTs for which the reordering operations will, in general be different. This is exemplified in the specific embodiment described below in which the apparatus can handle inverse and forward 840 point transforms and 94,168 and 420 point inverse transforms. A forward transform is from time domain to frequency domain and an inverse transform is from frequency domain to time domain.